/**
 * 494. 目标和
 * https://leetcode-cn.com/problems/target-sum/
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function findTargetSumWays(nums, target) {
  let sum = 0;
  for (let i = 0; i < nums.length; i += 1) {
    sum += nums[i];
  }
  const minuend = (sum - target) / 2;
  if (!Number.isInteger(minuend) || minuend < 0) {
    return 0;
  }
  let pre = new Array(minuend + 1).fill(0);
  pre[0] = 1;
  let cur = new Array(minuend + 1);
  for (let i = 1; i <= nums.length; i += 1) {
    cur.fill(0);
    const num = nums[i - 1];
    if (num === 0) {
      cur[0] = pre[0] * 2;
    } else {
      [cur[0]] = pre;
    }
    for (let j = 1; j <= minuend; j += 1) {
      if (num === j) {
        cur[j] = pre[j] + pre[0];
      } else if (num < j) {
        cur[j] = pre[j] + pre[j - num];
      } else {
        cur[j] = pre[j];
      }
    }
    const temp = pre;
    pre = cur;
    cur = temp;
  }
  return pre[minuend];
}

console.log(findTargetSumWays([1, 1, 1, 1, 1], 3) === 5);
console.log(findTargetSumWays([1], 1) === 1);
console.log(findTargetSumWays([1, 0], 1) === 2);
console.log(findTargetSumWays([1, 2, 1], 0) === 2);
console.log(findTargetSumWays([2, 107, 109, 113, 127, 131, 137, 3, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 47, 53], 1000) === 0);
